package kyssion.leetcode.num51_100;

import java.util.*;

public class code76_最小覆盖子串 {
    public static void main(String[] args) {
        System.out.println(new code76_最小覆盖子串().minWindow("aaaa", "aaa"));
    }

    public String minWindow(String s, String t) {

        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        Map<Character, Integer> oldItem = new HashMap<>();
        Map<Character, Integer> newItem = new HashMap<>();
        Deque<Integer> queue = new LinkedList<>();
        int needNum = 0;
        for (int a = 0; a < chart.length; a++) {
            if (!oldItem.containsKey(chart[a])) {
                oldItem.put(chart[a], 1);
                newItem.put(chart[a], 0);
            } else {
                oldItem.put(chart[a], oldItem.get(chart[a]) + 1);
            }
        }
        int before = 0;
        int end = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        while (right < chars.length) {
            if (oldItem.containsKey(chars[right])) {
                if (needNum < chars.length) {
                    int newNum = newItem.get(chars[right]) + 1;
                    if (newNum == oldItem.get(chars[right])) {
                        needNum+=newNum;
                    }
                    newItem.put(chars[right], newNum);
                    queue.addLast(right);
                }
                if (needNum == chart.length) {
                    while (needNum == chart.length) {
                        left = queue.removeFirst();
                        int newNum = newItem.get(chars[left]);
                        if (newNum - 1 < oldItem.get(chars[left])) {
                            needNum-=oldItem.get(chars[left]);
                        }
                        newItem.put(chars[left], newNum - 1);
                    }
                    if (right - left < end - before) {
                        before = left;
                        end = right;
                    }
                }
            }
            right++;
        }
        return end == Integer.MAX_VALUE ? "" : s.substring(before, end + 1);
    }

    /**
     * 写法上的优化
     * @param s
     * @param t
     * @return
     */
    public String minWindow2(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }
        char[] chas1 = s.toCharArray();
        char[] chas2 = t.toCharArray();
        int[] map = new int[256];  // 也可以用HashMap
        for (int i = 0; i < chas2.length; i++) {
            map[chas2[i]]++;
        }
        int left = 0;
        int right = 0;
        int match = chas2.length;
        int minLen = Integer.MAX_VALUE;
        int minLeft = 0;
        while (right < chas1.length) {
            map[chas1[right]]--;
            if (map[chas1[right]] >= 0) {
                match--;
            }
            if (match == 0) {
                while (map[chas1[left]] < 0) {
                    map[chas1[left++]]++;
                }
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                }
                match++;
                map[chas1[left++]]++;
            }
            right++;
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
    }
}
